package hot;

import java.util.ArrayList;
import java.util.List;

/**
 * @author lakersUp
 * @Classname   删除无效的括号
 * @Description     回溯加剪枝
 * @Date 2022/3/23 15:03
 * @Version 1.0
 */
public class Hot301removeInvalidParentheses {
    List<String> res = new ArrayList<>();
    public List<String> removeInvalidParentheses(String s) {
        int left=0;
        int right=0;
        for(int i=0;i<s.length();i++){
            if(s.charAt(i)=='('){
                left++;
            }else if(s.charAt(i)==')'){
                if(left>0){
                    left--;
                }else {
                    right++;
                }
            }
        }
        dfs(s,0,left,right);


        return res;
    }

    private void dfs(String str, int start, int left, int right) {
        if(left==0 && right==0){
            if(isValid(str)){
                res.add(str);
            }
            return;
        }
        for(int i=start;i<str.length();i++){
            if(i!=start && str.charAt(i)==str.charAt(i-1)){
                continue;
            }
            if(left+right>str.length()-i){
                return;
            }
            if(left>0 && str.charAt(i)=='('){
                dfs(str.substring(0,i)+str.substring(i+1),i,left-1,right);
            }
            if(right>0 && str.charAt(i)==')'){
                dfs(str.substring(0,i)+str.substring(i+1),i,left,right-1);
            }
        }

    }

    private boolean isValid(String str) {
        int cnt = 0;
        for (int i = 0; i < str.length(); i++) {
            if (str.charAt(i) == '(') {
                cnt++;
            } else if (str.charAt(i) == ')') {
                cnt--;
                if (cnt < 0) {
                    return false;
                }
            }
        }
        return cnt == 0;

    }

}
